//https://leetcode.cn/problems/combinations/

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

//public class Combinations01_01_77 {
//
//    List<List<Integer>> result = new ArrayList<>();
//    LinkedList<Integer> path = new LinkedList<>();
//
//    public List<List<Integer>> combine(int n, int k) {
//        backtracking(n,k,1);
//        return result;
//    }
//
//    private void backtracking(int n, int k, int startIndex) {
//        if(path.size() == k) {
//            result.add(new ArrayList<>(path));
//            return;
//        }
//
//        for (int j = startIndex; j <= n; j++) {
//            path.add(j);
//            backtracking(n,k,j+1);
//            path.removeLast();
//        }
//    }
//}

//剪枝操作

public class Combinations01_02_77 {

    List<List<Integer>> result = new ArrayList<>(); // 二维数组 返回值
    LinkedList<Integer> path = new LinkedList<>(); //一位数组 每一个符合条件的值

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }

    private void backtracking(int n, int k, int startIndex) {

        //终止 当path大小满足k时，
        if(path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        //n - (k - path.size()) + 1
        for (int i = startIndex; i <= n - (k - path.size()) + 1 ; i++) {
            path.add(i);
            backtracking(n,k,i+1);
            path.removeLast();
        }
    }

}
